//
// Created by 抑~风 on 2022/12/13.
//

#ifndef BPLUSDATABASE_CWJBPLUSSE_H
#define BPLUSDATABASE_CWJBPLUSSE_H

#include <cstdio>
#include<cstring>
#include <cassert>
#include <iostream>
#include<algorithm>
#include <queue>
#include<unordered_map>

using namespace std;
namespace CWJ::BPlusSE {


    // B+树的元信息
    struct Meta {
        // 树的高度
        size_t height = 0;
        // 叶子的数目
        size_t leafNum = 0;
        // 根节点在文件中的偏移
        off_t rootOt = 0;
        // 空间分配池的起始点
        off_t slot = 0;
//        off_t leafHead = 0;
        size_t valNum = 0;

        friend ostream &operator<<(ostream &os, const Meta &meta) {
            os << "height: " << meta.height << " leafNum: " << meta.leafNum << " rootOt: " << meta.rootOt << " slot: "
               << meta.slot << " valNum: " << meta.valNum;
            return os;
        }

    };

    template<typename Key, typename Value>
    struct Item {
        Key key;
        Value val;
    };

    // 叶子节点
    template<typename Key, typename Value, int order>
    struct LeafNode {
        // 父节点在磁盘文件的偏移
        off_t parent = 0;
        //儿子数目
        size_t n = 0;
        // 下一个节点
        off_t next = 0;
        using Item = Item<Key, Value>;
        // 子节点
        Item childs[order];

        Item *begin() { return childs; };

        Item *end() { return childs + n; };
    };

    // 内部节点
    template<typename Key, int order>
    struct InternalNode {
        using Item = Item<Key, off_t>;
        off_t parent = 0;
        size_t n = 0;
        Item childs[order];

        inline void addChilds(const Item &item) {
            assert(this->n < order);
            childs[this->n] = item;
            this->n++;
        }

        Item *begin() { return childs; };

        Item *end() { return childs + n; };
    };

    const static size_t NODE_SPACE_SIZE = 16 * 1024;

    // B+树结构
    template<typename Key,
            typename Value,
            int leafOrder = (NODE_SPACE_SIZE - 2 * sizeof(off_t) - sizeof(size_t)) / sizeof(Item<Key, Value>),
            int internalOrder = (NODE_SPACE_SIZE - sizeof(off_t) - sizeof(size_t)) / sizeof(Item<Key, off_t>)>
    class BPlusTree {
    public:

        using InternalNode = CWJ::BPlusSE::InternalNode<Key, internalOrder>;
        using LeafNode = CWJ::BPlusSE::LeafNode<Key, Value, leafOrder>;
        using Item = Item<Key, Value>;
        using InternalNodeItem = typename InternalNode::Item;

        const static size_t PATH_LEN = 120;
        const static size_t META_OFFSET = 0;
        static off_t ROOT_PARENT;

        // 注意：因为默认拷贝构造函数的存在，curBegItr,curEndItr仍然和传入的指针一样，
        // 但是其curLeaf是重新生成的，所以其会导致curBegItr,curEndItr不再是执行curLeaf的指针了
        // 所以会出现错误
        class iterator : public std::iterator<std::input_iterator_tag, Item> {
        public:

            const static off_t NULL_OT = 0;

            const static iterator ENDITR;

            iterator(BPlusTree<Key, Value, leafOrder, internalOrder> *tree, off_t minOt, Key minKey,
                     Key maxKey, bool isMax = false, bool isMin = false, bool isEnd = false) : tree(tree),
                                                                                               minKey(minKey),
                                                                                               maxKey(maxKey),
                                                                                               curOt(minOt),
                                                                                               isMax(isMax),
                                                                                               isMin(isMin),
                                                                                               isEnd(isEnd) {
                if (curOt != NULL_OT) {
                    updateNextLeaf(curOt);
                } else {
                    curEndInd = leafOrder;
                }
            }

            void updateNextLeaf(off_t ot) {
                this->curOt = ot;
                tree->load(&curLeaf, ot, sizeof(LeafNode));


                if (isMin) {
                    curBegInd = 0;
                } else {
                    curBegInd = lower_bound(curLeaf.begin(), curLeaf.end(), minKey,
                                            [](const auto &e, const Key &key) { return e.key < key; }) -
                                curLeaf.begin();
                }

                if (isMax) curEndInd = this->curLeaf.n;
                else {
                    curEndInd = upper_bound(curLeaf.begin(), curLeaf.end(), maxKey,
                                            [](const Key &key, const auto &e) { return key < e.key; }) -
                                this->curLeaf.begin();
                }

            }

            typename iterator::reference operator*() {
                assert(this->curBegInd != this->curLeaf.n);
                return *(this->curLeaf.begin() + this->curBegInd);
            }

            typename iterator::pointer const operator->() {
                assert(this->curBegInd != this->curLeaf.n);
                return (this->curLeaf.begin() + this->curBegInd);
            }

            iterator &operator++() {
                auto tt = this->curLeaf.end();
                if (curBegInd + 1 != curEndInd) {
                    curBegInd++;
                } else if (curEndInd == this->curLeaf.n && curLeaf.next != NULL_OT) {
                    this->updateNextLeaf(curLeaf.next);
                } else {
                    (*this) = iterator::ENDITR;
                }

                return *this;
            }

            iterator operator++(int) {
                iterator temp(*this);
                ++*this;
                return temp;
            }

            bool operator==(const iterator &rhs) const {
                return curOt == rhs.curOt &&
                       curBegInd == rhs.curBegInd;
            }

            bool operator!=(const iterator &rhs) const {
                return !(rhs == *this);
            }

        private:

            BPlusTree<Key, Value, leafOrder, internalOrder> *tree;
            Key minKey;
            bool isMax;
            Key maxKey;
            bool isMin;
            off_t curOt;
            LeafNode curLeaf;
            bool isEnd;
            size_t curBegInd;
            size_t curEndInd;

        };


        BPlusTree(const char *path, bool forceEmpty = true);

        bool insert(const Key &key, const Value &value);



        void insertOrderBatch(const vector<pair<Key, Value>> &items);

        void insertUnOrderBatch(vector<pair<Key, Value>> items);

        bool remove(const Key &key);

        bool searchKey(const Key &key, Value &val);

        iterator searchRange(const Key &minKey, const Key &maxKey);

        iterator searchRange(const Key &minKey);


        void showTree();

        iterator begin();

        iterator end();

    private:
        using NodeMap = std::unordered_map<size_t, pair<off_t, InternalNode>>  ;
        using NodeMapVal = pair<off_t, InternalNode>;
        void showTree(off_t ot, int height, string text);

        void showNode(InternalNode *itNode, string text);

        void showNode(LeafNode *leaf, string text);

        off_t searchIndex(const Key &key);

        void searchIndex(const Key &key,NodeMap& nodeMap);

        off_t searchLeaf(const Key &key);

        void searchLeaf(const Key &key,NodeMap& nodeMap,pair<off_t,LeafNode>&leafItem);

        bool insert(const Key &key, const Value &value, NodeMap &nodeMap,pair<off_t,LeafNode>&leafBak);

        off_t searchLeaf(InternalNode *itNode, const Key &key);

        bool borrowLeaf(LeafNode *cur, off_t otherOt, bool isNext);

        bool borrowIndex(off_t curOt, InternalNode *cur, off_t otherOt, bool isNext);

        void changeParentChildKey(off_t ot, const Key &oldKey, const Key &newKey);

        void insertKeyToLeafNoSplit(LeafNode *leaf, const Key &key, const Value &val);

        void insertKeyToIndex(off_t indOt, const Key &key, off_t newSonOt, bool sonIsLeaf);

        void insertKeyToIndexNoSplit(InternalNode *itNode, const Key &key, off_t newSonOt);

        bool insertRepeatRecordToLeaf(LeafNode *leaf, const Key &key, const Value &val);

        template<typename T>
        void mergeNode(T *lef, T *rig);

        void removeKeyFromIndex(off_t ot, InternalNode *itNode, const Key &key);

        void resetIndexChildParent(typename InternalNode::Item *beg, typename InternalNode::Item *ed, off_t parent);

//        void resetLeafChildParent(typename LeafNode::Item *beg, typename LeafNode::Item *ed, off_t parent);

        void store(void *block, off_t offSet, size_t len);

        bool load(void *block, off_t offSet, size_t len);

        void openFile(const char *mode = "rb+");

        void closeFile();

        void initTree();

        off_t alloc(size_t size);

        static bool lessLeaf(const Key &key, const Item &e) {
            return key < e.key;
        }

        static bool lessInternal(const Key &key, const InternalNodeItem &e) {
            return key < e.key;
        }

        // B+树的原信息
        Meta meta;
        // 数据库文件路径
        char path[PATH_LEN];
        // 打开的文件夹的描述符
        FILE *fd;
        //当前有多少个函数打开文件，避免重复关闭，或是提前关闭
        size_t fdNum = 0;
    };

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    off_t BPlusTree<Key, Value, leafOrder, internalOrder>::ROOT_PARENT = 0;

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    BPlusTree<Key, Value, leafOrder, internalOrder>::BPlusTree(const char *path, bool forceEmpty) {
        memset(this->path, 0, PATH_LEN);
        memcpy(this->path, path, strlen(path));

        if (!forceEmpty) {
            // 读入数据库文件,一般B树在内存中仅仅需要存储其源信息，因为其拥有指向根节点的偏移量
            if (!this->load(&this->meta, META_OFFSET, sizeof(Meta))) {
                forceEmpty = true;
            }
        }

        if (forceEmpty) {
            this->openFile("w+");
            this->initTree();
            this->closeFile();
        }
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::store(void *block, off_t offSet, size_t len) {
        this->openFile();
        if(len != sizeof(Meta))

        fseek(this->fd, offSet, SEEK_SET);

        int res = fwrite(block, len, 1, this->fd);

        assert(res == 1);

        this->closeFile();
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::load(void *block, off_t offSet, size_t len) {
        this->openFile();
        fseek(this->fd, offSet, SEEK_SET);

        int res = fread(block, len, 1, this->fd);
//        assert(res == 1);
        if (res != 1)cerr << "load : 无法读入" << endl;
        this->closeFile();
        return res == 1;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::openFile(const char *mode) {
        if (!this->fdNum) this->fd = fopen(this->path, mode);

        this->fdNum++;
        if (this->fd == nullptr)
            cerr << "error : BPlusTree<Key, Value, leafOrder, internalOrder>::openFile : "
                    "this->fd == nullptr" << endl;
//        assert(this->fd != nullptr);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::closeFile() {
        if (!this->fdNum) return;
        this->fdNum--;
        if (!this->fdNum) fclose(this->fd);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::initTree() {

        memset(&this->meta, 0, sizeof(Meta));
        this->meta.slot = META_OFFSET + sizeof(Meta);
        this->meta.height = 2;
        this->meta.leafNum = 1;
        this->meta.valNum = 0;

        // 初始化 根节点

        InternalNode root;
        this->meta.rootOt = this->alloc(sizeof(root));

        // 初始化第一个叶子节点

        LeafNode leaf;
        off_t leafOt = 0;
        root.addChilds({Key(), leafOt = alloc(sizeof(LeafNode))});
        leaf.parent = this->meta.rootOt;
//        this->meta.leafHead = leafOt;


        this->store(&meta, META_OFFSET, sizeof(Meta));
        this->store(&root, this->meta.rootOt, sizeof(root));
        this->store(&leaf, leafOt, sizeof(leaf));

    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    off_t BPlusTree<Key, Value, leafOrder, internalOrder>::alloc(size_t size) {
        off_t res = this->meta.slot;
        this->meta.slot += size;
        return res;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::insert(const Key &key, const Value &value) {

        // TODO 需要优化
        off_t leafOt = this->searchLeaf(key);
        LeafNode leaf;

        this->load(&leaf, leafOt, sizeof(LeafNode));

        // 需要判断是否存在重复
        int tmp = 0;
        if (this->insertRepeatRecordToLeaf(&leaf, key, value)) {
            this->store(&leaf, leafOt, sizeof(LeafNode));
            return true;
        }

        if (leaf.n == leafOrder) {
            // 需要分裂叶子节点

            // 新建节点并初始化
            LeafNode new_leaf;

            new_leaf.parent = leaf.parent;
            new_leaf.next = leaf.next;
            new_leaf.n = 0;
            leaf.next = alloc(sizeof(LeafNode));
            this->meta.leafNum++;

            int point = leaf.n / 2;

            bool placeRight = (leaf.begin() + point)->key < key;

            if (placeRight) point++;

            std::copy(leaf.begin() + point, leaf.end(), new_leaf.begin());

            new_leaf.n = leaf.n - point;
            leaf.n = point;

            if (placeRight) {
                insertKeyToLeafNoSplit(&new_leaf, key, value);
            } else insertKeyToLeafNoSplit(&leaf, key, value);


            this->store(&leaf, leafOt, sizeof(LeafNode));
            this->store(&new_leaf, leaf.next, sizeof(LeafNode));

            // 将m/2处的关键字插入内部节点中
            this->insertKeyToIndex(leaf.parent, (leaf.end() - 1)->key, leaf.next, true);

        } else {
            insertKeyToLeafNoSplit(&leaf, key, value);
            this->store(&leaf, leafOt, sizeof(LeafNode));
        }

        this->store(&this->meta, META_OFFSET, sizeof(Meta));

        return false;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    off_t BPlusTree<Key, Value, leafOrder, internalOrder>::searchIndex(const Key &key) {

        int h = this->meta.height;
        off_t ot = this->meta.rootOt;
        while (h > 2) {
            InternalNode node;
            this->load(&node, ot, sizeof(node));
            auto it = lower_bound(node.begin(), node.end() - 1, key,
                                  [](const auto &e, const Key &key) { return e.key < key; });
            ot = it->val;
            --h;
        }
        return ot;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    off_t BPlusTree<Key, Value, leafOrder, internalOrder>::searchLeaf(const Key &key) {

        off_t ot = this->searchIndex(key);

        InternalNode node;

        this->load(&node, ot, sizeof(InternalNode));

        auto it = lower_bound(node.begin(), node.end() - 1, key,
                              [](const auto &e, const Key &key) { return e.key < key; });
        ot = it->val;

        return ot;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::insertKeyToLeafNoSplit(LeafNode *leaf, const Key &key,
                                                                                 const Value &val) {


        Item *it = lower_bound(leaf->begin(), leaf->end(), key,
                               [](const auto &e, const Key &key) { return e.key < key; });
        if (it != leaf->end() && it->key == key) {
            it->val = val;
            return;
        }
        std::copy_backward(it, leaf->end(), leaf->end() + 1);
        it->key = key;
        it->val = val;
        leaf->n++;
        this->meta.valNum++;
        return;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::insertKeyToIndex(off_t indOt, const Key &key, off_t nextSonOt,
                                                                           bool sonIsLeaf) {

        if (indOt == 0) {



            InternalNode root;

            root.parent = 0;
            root.n = 2;
            root.childs[0].key = key;
            off_t oldRootOt = root.childs[0].val = this->meta.rootOt;
            root.childs[1].key = Key();
            root.childs[1].val = nextSonOt;

            this->meta.rootOt = this->alloc(sizeof(InternalNode));

            this->resetIndexChildParent(root.begin(), root.end(), this->meta.rootOt);

//            cout<<"show root"<<endl;
//
//            this->showNode(&root,"****");

            this->store(&this->meta, META_OFFSET, sizeof(Meta));
            this->store(&root, this->meta.rootOt, sizeof(InternalNode));
            this->meta.height++;

            return;
        }


        InternalNode itNode;
        this->load(&itNode, indOt, sizeof(InternalNode));


        if (itNode.n == internalOrder) {

            // 分裂节点
            InternalNode new_node;
            new_node.parent = itNode.parent;
            new_node.n = 0;
            off_t newItOt = alloc(sizeof(InternalNode));
            int point = itNode.n / 2;

            bool place_right = ((itNode.begin() + point - 1)->key < key);

            std::copy(itNode.begin() + point, itNode.end(), new_node.begin());

            new_node.n = itNode.n - point;
            itNode.n = point;


            if (place_right) this->insertKeyToIndexNoSplit(&new_node, key, nextSonOt);
            else this->insertKeyToIndexNoSplit(&itNode, key, nextSonOt);

//            cout<<"show itNode:"<<indOt<<endl;
//            this->showNode(&itNode,"    ");
//
//            cout<<"show new_node:"<<newItOt<<endl;
//            this->showNode(&new_node,"    ");


            this->resetIndexChildParent(new_node.begin(), new_node.end(), newItOt);

            this->store(&itNode, indOt, sizeof(InternalNode));
            this->store(&new_node, newItOt, sizeof(InternalNode));
            // 继续将新关键字以及新的节点查到父节点中，递归，直到到达根节点
            this->insertKeyToIndex(itNode.parent, (itNode.end() - 1)->key, newItOt, false);

        } else {
            this->insertKeyToIndexNoSplit(&itNode, key, nextSonOt);
            this->store(&itNode, indOt, sizeof(InternalNode));


        }
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::insertKeyToIndexNoSplit(InternalNode *itNode, const Key &key,
                                                                                  off_t newSonOt) {

        InternalNodeItem *it = lower_bound(itNode->begin(),
                                           itNode->end() - 1,
                                           key,
                                           [](const auto &e, const Key &key) { return e.key < key; });

        assert(it->key != key);

        std::copy_backward(it, itNode->end(), itNode->end() + 1);
        it->key = key; // 原来位置的key发生改变，但是val不需要改变
        it->val = (it + 1)->val;
        (it + 1)->val = newSonOt;

        itNode->n++;

    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::resetIndexChildParent(typename InternalNode::Item *beg,
                                                                                typename InternalNode::Item *ed,
                                                                                off_t parent) {
        while (beg != ed) {
            InternalNode itNode;

            this->load(&itNode, beg->val, sizeof(off_t));


            itNode.parent = parent;

            this->store(&itNode, beg->val, sizeof(off_t));

            beg++;
        }

    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::showTree() {

        cout << "---------------- showTree -----------------" << endl;
        cout << "height:" << this->meta.height << endl;
        this->showTree(this->meta.rootOt, this->meta.height, "");
        return;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::showTree(off_t ot, int height, string text) {
        if (height == 1) {
            LeafNode leaf;
            this->load(&leaf, ot, sizeof(LeafNode));
            cout<<text<<" leaf "<<leaf.n<<" fa :"<<leaf.parent<<endl;
            this->showNode(&leaf, text);
            return;
        }

        InternalNode itNode;
        this->load(&itNode, ot, sizeof(InternalNode));
        cout<<text<<"itNode"<<itNode.n<<" fa :"<<itNode.parent<<endl;
        for (typename InternalNode::Item *it = itNode.begin(); it != itNode.end(); it++) {
            cout << text<<ot<< "son :" << it->key << " ot:  " << it->val<< endl;
            showTree(it->val, height - 1, text + "    ");
        }

        return;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::showNode(InternalNode *itNode, string text) {
        for (typename InternalNode::Item *it = itNode->begin(); it != itNode->end(); it++) {
            cout << text << it->key << " " << it->val << endl;
        }

    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::showNode(LeafNode *leaf, string text) {
        for (typename LeafNode::Item *it = leaf->begin(); it != leaf->end(); it++) {
            cout << text << it->key << " " << it->val << endl;
        }
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::insertRepeatRecordToLeaf(LeafNode *leaf, const Key &key,
                                                                                   const Value &val) {
        Item *it = lower_bound(leaf->begin(), leaf->end(), key,
                               [](const auto &e, const Key &key) { return e.key < key; });
        if (it != leaf->end() && it->key == key) {
            it->val = val;
            return true;
        }
        return false;
    }

//    template<typename Key, typename Value, int order>
//    void BPlusTree<Key, Value, order>::resetLeafChildParent(typename LeafNode::Item *beg,
//                                                            typename LeafNode::Item *ed,
//                                                            off_t parent) {
//
//        while (beg != ed) {
//            LeafNode itNode;
//
//            this->load(&itNode, beg->val, sizeof(off_t));
//
//            itNode.parent = parent;
//
//            this->store(&itNode, beg->val, sizeof(off_t));
//
//            beg++;
//        }
//
//
//    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::remove(const Key &key) {
        off_t parentOt = this->searchIndex(key);
        InternalNode itNode;
        this->load(&itNode, parentOt, sizeof(InternalNode));


        // 删除节点
        auto itNodeItr = lower_bound(itNode.begin(), itNode.end() - 1, key,
                                     [](const auto &e, const Key &key) { return e.key < key; });

        off_t leafOt = itNodeItr->val;
        LeafNode leaf;
        this->load(&leaf, leafOt, sizeof(LeafNode));

        // 删除节点
        auto it = lower_bound(leaf.begin(), leaf.end() - 1, key,
                              [](const auto &e, const Key &key) { return e.key < key; });

        if (it == leaf.end() || it->key != key) { return false; };


        // delete

        if (it == leaf.end() - 1 && it != leaf.begin()) this->changeParentChildKey(leaf.parent, it->key, (it - 1)->key);

        std::copy(it + 1, leaf.end(), it);
        leaf.n--;


        int minN = this->meta.leafNum == 1 ? 0 : leafOrder / 2;

        if (leaf.n < minN) {
            bool isBorrow = false;
            // 借节点，先先后借，再向前借
            if (itNodeItr != (itNode.end() - 1) && this->borrowLeaf(&leaf, (itNodeItr + 1)->val, true)) {
                isBorrow = true;
            } else if (itNodeItr != itNode.begin() && this->borrowLeaf(&leaf, (itNodeItr - 1)->val, false)) {
                isBorrow = true;
            }

            // 借不到就合并
            if (!isBorrow) {


                Key removedKey;

                if (itNodeItr != (itNode.end() - 1)) {

                    LeafNode nextLeaf;

                    off_t nextOt = (itNodeItr + 1)->val;

                    this->load(&nextLeaf, nextOt, sizeof(LeafNode));
                    this->template mergeNode(&leaf, &nextLeaf);

                    // 移除next叶子节点
                    leaf.next = nextLeaf.next;
                    // 要在父节点移除的键值
                    removedKey = (itNodeItr)->key;

                    this->store(&leaf, leafOt, sizeof(LeafNode));

                    this->meta.leafNum--;


                } else if (itNodeItr != itNode.begin()) {

                    LeafNode prevLeaf;

                    off_t prevOt = (itNodeItr - 1)->val;

                    this->load(&prevLeaf, prevOt, sizeof(LeafNode));
                    this->template mergeNode(&prevLeaf, &leaf);

                    prevLeaf.next = leaf.next;

                    removedKey = (itNodeItr - 1)->key;

                    this->store(&prevLeaf, prevOt, sizeof(LeafNode));

                    this->meta.leafNum--;

                }

                this->store(&this->meta, META_OFFSET, sizeof(Meta));
                this->removeKeyFromIndex(parentOt, &itNode, removedKey);

            } else {
                this->store(&leaf, leafOt, sizeof(LeafNode));
            }

        } else {
            this->store(&leaf, leafOt, sizeof(LeafNode));
        }

        return true;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    off_t BPlusTree<Key, Value, leafOrder, internalOrder>::searchLeaf(InternalNode *itNode, const Key &key) {
        auto it = lower_bound(itNode->begin(), itNode->end() - 1, key,
                              [](const auto &e, const Key &key) { return e.key < key; });
        return it->val;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::borrowLeaf(LeafNode *cur, off_t otherOt, bool isNext) {


        int minN = this->meta.leafNum == 1 ? 0 : leafOrder / 2;

        LeafNode other;
        this->load(&other, otherOt, sizeof(LeafNode));
        assert(other.n >= minN);


        if (other.n <= minN) return false;
        else {

            typename LeafNode::Item *whereToLend = nullptr, *whereToPut = nullptr;


            if (isNext) {
                whereToLend = other.begin();
                whereToPut = cur->end();
                // 调整索引节点

                this->changeParentChildKey(cur->parent, (whereToPut - 1)->key, whereToLend->key);
            } else {
                whereToLend = other.end() - 1;
                whereToPut = cur->begin();
                this->changeParentChildKey(cur->parent, whereToLend->key, (whereToLend - 1)->key);
            }

            // borrow
            std::copy_backward(whereToPut, cur->end(), cur->end() + 1);
            whereToPut->key = whereToLend->key;
            whereToPut->val = whereToLend->val;

            cur->n++;


            // erase
            std::copy_backward((whereToLend + 1), other.end(), other.end() - 1);
            other.n--;
            this->store(&other, otherOt, sizeof(LeafNode));
            return true;

        }


    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::changeParentChildKey(off_t ot, const Key &oldKey,
                                                                               const Key &newKey) {
        InternalNode itNode;
        this->load(&itNode, ot, sizeof(InternalNode));

        auto it = lower_bound(itNode.begin(), itNode.end() - 1, oldKey,
                              [](const auto &e, const Key &key) { return e.key < key; });

        it->key = newKey;

        this->store(&itNode, ot, sizeof(InternalNode));

        // 如果修改最值，那么就需要更新父节点
        if (itNode.parent && it == itNode.end() - 1) {
            this->changeParentChildKey(itNode.parent, oldKey, newKey);
        }

    }


    template<typename Key, typename Value, int leafOrder, int internalOrder>
    template<typename T>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::mergeNode(T *lef, T *rig) {
        std::copy(rig->begin(), rig->end(), lef->end());
        lef->n += rig->n;
        rig->n = 0;

        return;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::removeKeyFromIndex(off_t ot, InternalNode *itNode,
                                                                             const Key &key) {


        auto it = lower_bound(itNode->begin(), itNode->end() - 1, key,
                              [](const auto &e, const Key &key) { return e.key < key; });


        if (it != itNode->end() && it->key == key) {
            if (it != itNode->end() - 1) {
                (it + 1)->val = it->val;
            }
            std::copy(it + 1, itNode->end(), it);
            itNode->n--;
        }

        // 根节点至少有两个分支,判断是否在根节点
        if (ot == this->meta.rootOt) {
            if (itNode->n == 1 && this->meta.height > 2) {
                // 移除根节点
                this->meta.rootOt = itNode->begin()->val;
                this->meta.height--;

                this->store(&this->meta, META_OFFSET, sizeof(Meta));
                this->store(&ROOT_PARENT, this->meta.rootOt, sizeof(off_t));
            }
            this->store(itNode, ot, sizeof(InternalNode));
            return;
        }


        size_t min_n = itNode->parent == 0 ? 1 : internalOrder / 2;

        if (itNode->n < min_n) {

            InternalNode faNode;
            this->load(&faNode, itNode->parent, sizeof(InternalNode));

            auto itr = lower_bound(faNode.begin(), faNode.end() - 1, (itNode->end() - 1)->key,
                                   [](const auto &e, const Key &key) { return e.key < key; });

            bool isBorrow = false;

            if (itr != faNode.end() - 1 && this->borrowIndex(ot, itNode, (itr + 1)->val, true)) {
                isBorrow = true;
            } else if (itr != faNode.begin() && this->borrowIndex(ot, itNode, (itr - 1)->val, false)) {
                isBorrow = true;
            }

            if (!isBorrow) {

                // 合并
                Key removedKey;

                if (itr != (faNode.end() - 1)) {
                    InternalNode nextNode;
                    off_t nextOt = (itr + 1)->val;
                    this->load(&nextNode, nextOt, sizeof(InternalNode));
                    this->resetIndexChildParent(nextNode.begin(), nextNode.end(), ot);
                    this->template mergeNode(itNode, &nextNode);

                    removedKey = (itr)->key;

//                    this->showNode(itNode,"   ");

                    this->store(itNode, ot, sizeof(InternalNode));

                } else if (itr != faNode.begin()) {
                    InternalNode prevNode;
                    off_t prevOt = (itr - 1)->val;
                    this->load(&prevNode, prevOt, sizeof(InternalNode));
                    this->resetIndexChildParent(itNode->begin(), itNode->end(), (itr - 1)->val);
                    this->template mergeNode(&prevNode, itNode);

                    removedKey = (itr - 1)->key;

                    this->store(&prevNode, prevOt, sizeof(InternalNode));

                }

                this->removeKeyFromIndex(itNode->parent, &faNode, removedKey);

            } else {
                this->store(itNode, ot, sizeof(InternalNode));
            }


        } else {
            this->store(itNode, ot, sizeof(InternalNode));
        }


    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::borrowIndex(off_t curOt, InternalNode *cur, off_t otherOt,
                                                                      bool isNext) {

        int min_n = internalOrder / 2;

        InternalNode other;

        this->load(&other, otherOt, sizeof(InternalNode));

        assert(other.n >= min_n && other.n <= internalOrder);

        if (other.n > min_n) {
            typename InternalNode::Item *whereToLend = nullptr, *whereToPut = nullptr;

            if (isNext) {
                whereToLend = other.begin();
                whereToPut = cur->end();
                // 调整索引节点
                this->changeParentChildKey(cur->parent, (whereToPut - 1)->key, whereToLend->key);
            } else {
                whereToLend = other.end() - 1;
                whereToPut = cur->begin();
                this->changeParentChildKey(cur->parent, whereToLend->key, (whereToLend - 1)->key);
            }

            // borrow
            std::copy_backward(whereToPut, cur->end(), cur->end() + 1);
            whereToPut->key = whereToLend->key;
            whereToPut->val = whereToLend->val;
            cur->n++;
            this->resetIndexChildParent(whereToLend, whereToLend + 1, curOt);
            // erase


            std::copy_backward((whereToLend + 1), other.end(), other.end() - 1);
            other.n--;

            this->store(&other, otherOt, sizeof(LeafNode));

            return true;

        }

        return false;


    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::searchKey(const Key &key, Value &val) {
        off_t ot = this->searchLeaf(key);
        LeafNode leaf;
        this->load(&leaf, ot, sizeof(leaf));
        Item *it = lower_bound(leaf.begin(), leaf.end(), key,
                               [](const auto &e, const Key &key) { return e.key < key; });
        if (it != leaf.end() && it->key == key) {
            val = it->val;
            return true;
        }
        return false;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    typename BPlusTree<Key, Value, leafOrder, internalOrder>::iterator
    BPlusTree<Key, Value, leafOrder, internalOrder>::searchRange(const Key &minKey, const Key &maxKey) {
        off_t minOt = this->searchLeaf(minKey);
        return iterator(this, minOt, minKey, maxKey);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    typename BPlusTree<Key, Value, leafOrder, internalOrder>::iterator
    BPlusTree<Key, Value, leafOrder, internalOrder>::begin() {

        if (this->meta.valNum < 1) return this->end();

        int h = this->meta.height;
        off_t ot = this->meta.rootOt;
        while (h > 1) {
            InternalNode node;
            this->load(&node, ot, sizeof(node));

            if (node.n < 1) return this->end();

            ot = node.begin()->val;
            --h;
        }
        return iterator(this, ot, Key(), Key(), true, true);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    typename BPlusTree<Key, Value, leafOrder, internalOrder>::iterator
    BPlusTree<Key, Value, leafOrder, internalOrder>::end() {
        return iterator::ENDITR;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    typename BPlusTree<Key, Value, leafOrder, internalOrder>::iterator
    BPlusTree<Key, Value, leafOrder, internalOrder>::searchRange(const Key &minKey) {
        off_t minOt = this->searchLeaf(minKey);
        return BPlusTree::iterator(this, minOt, minKey, Key(), true, false);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    bool BPlusTree<Key, Value, leafOrder, internalOrder>::insert(const Key &key, const Value &value,
                                                                 std::unordered_map<size_t, pair<off_t, InternalNode>> &nodeMap,pair<off_t,LeafNode>&leafItem) {

        // TODO 需要优化
        // 载入叶子节点
        this->searchLeaf(key,nodeMap,leafItem);

        off_t leafOt = leafItem.first;
        LeafNode & leaf = leafItem.second;

        // 需要判断是否存在重复
        int tmp = 0;
        if (this->insertRepeatRecordToLeaf(&leaf, key, value)) {
            return true;
        }

        if (leaf.n == leafOrder) {

            this->store(&this->meta, META_OFFSET, sizeof(Meta));

            // 如果需要分裂的话，就情况缓存
            nodeMap.clear();


            // 需要分裂叶子节点
            // 新建节点并初始化
            LeafNode new_leaf;

            new_leaf.parent = leaf.parent;
            new_leaf.next = leaf.next;
            new_leaf.n = 0;
            leaf.next = this->alloc(sizeof(LeafNode));
            this->meta.leafNum++;

            int point = leaf.n / 2;

            bool placeRight = (leaf.begin() + point)->key < key;

            if (placeRight) point++;

            std::copy(leaf.begin() + point, leaf.end(), new_leaf.begin());

            new_leaf.n = leaf.n - point;
            leaf.n = point;

            if (placeRight) {
                insertKeyToLeafNoSplit(&new_leaf, key, value);
            } else insertKeyToLeafNoSplit(&leaf, key, value);

            // 优化
            this->store(&leaf, leafOt, sizeof(LeafNode));
            this->store(&new_leaf, leaf.next, sizeof(LeafNode));

            // 将m/2处的关键字插入内部节点中
            this->insertKeyToIndex(leaf.parent, (leaf.end() - 1)->key, leaf.next, true);


            // 注意：这句非常重要，因为我们需要向上添加索引，而在添加索引的时候我们磁盘中的叶子节点的父节点会发送改变，
            // 从而导致磁盘中和内存中的叶子节点的数据不一致从而导致错误
            leafItem.first = 0;

        } else {
            insertKeyToLeafNoSplit(&leaf, key, value);
        }



        return false;
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::insertOrderBatch(const vector<pair<Key, Value>> &items) {
        NodeMap nodeMap;
        std::pair<off_t,LeafNode> leafItem{0,LeafNode()};

        for(const auto& o : items){
            this->insert(o.first,o.second,nodeMap,leafItem);
        }
        this->store(&this->meta, META_OFFSET, sizeof(Meta));
        if(leafItem.first){
            this->store(&leafItem.second,leafItem.first,sizeof(LeafNode));
        }
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::insertUnOrderBatch(vector<pair<Key, Value>> items) {
        sort(items.begin(),items.end(),[](auto&a,auto&b){return a.first < b.first;});
        this->insertOrderBatch(items);
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::searchLeaf(const Key &key, BPlusTree::NodeMap &nodeMap,pair<off_t,LeafNode>&leafItem) {

        off_t ot = 0;

        this->searchIndex(key,nodeMap);

        auto &item = nodeMap[this->meta.height-1];
        InternalNode& node = item.second;

        auto it = lower_bound(node.begin(), node.end() - 1, key,
                              [](const auto &e, const Key &key) { return e.key < key; });
        ot = it->val;

        if(ot != leafItem.first){
            // 必须保证保存的leaf是有效的，否则就不保存
            if(leafItem.first) this->store(&leafItem.second,leafItem.first,sizeof(LeafNode));
            leafItem.first = ot;
            this->load(&leafItem.second,ot,sizeof(LeafNode));
        }

        return ;

    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    void BPlusTree<Key, Value, leafOrder, internalOrder>::searchIndex(const Key &key, BPlusTree::NodeMap &nodeMap) {
        int h = this->meta.height,curH = 1;
        off_t ot = this->meta.rootOt;
        while (curH <= h-1) {

            if(!nodeMap.count(curH)){
                nodeMap[curH] = {0,InternalNode()};
            }
            auto &item = nodeMap[curH];
            InternalNode &node = nodeMap[curH].second;
            if(item.first != ot){
                nodeMap[curH].first = ot;
                this->load(&node, ot, sizeof(node));
            }
            auto it = lower_bound(node.begin(), node.end() - 1, key,
                                  [](const auto &e, const Key &key) { return e.key < key; });
            ot = it->val;
            curH++;
        }
    }

    template<typename Key, typename Value, int leafOrder, int internalOrder>
    const typename BPlusTree<Key, Value, leafOrder, internalOrder>::iterator
            BPlusTree<Key, Value, leafOrder, internalOrder>::iterator::ENDITR(
            nullptr, BPlusTree<Key, Value, leafOrder, internalOrder>::iterator::NULL_OT, Key(), Key());
}


#endif //BPLUSDATAB// ASE_CWJBPLUSSE_H
